// https://www.lintcode.com/problem/binary-tree-upside-down/description

// 649. Binary Tree Upside Down
// Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

// Example
// Given a binary tree {1,2,3,4,5}

//     1
//    / \
//   2   3
//  / \
// 4   5
// return the root of the binary tree {4,5,2,#,#,3,1}.

//    4
//   / \
//  5   2
//     / \
//    3   1  

// 这样转的：
//     1
//    /
//   2 - 3
//  /
// 4 - 5
// 是先翻转当前节点再递归(a)，还是先递归再翻转当前节点(b)?
// 怎样做使得上下节点互不影响，(a)会忘了后面的值。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of binary tree
     * @return: new root
     */
    // TreeNode * upsideDownBinaryTree(TreeNode * root) {
    //     stack<TreeNode *> s;
    //     TreeNode * head;
    //     while (root)
    //     {
    //         s.push(root);
    //         root = root->left;
    //     }
    //     head = s.top();
    //     while (!s.empty())
    //     {
    //         root = s.top();
    //         s.pop();
    //         if (s.empty())
    //         {
    //             root->left = root->right = NULL;
    //             break;
    //         }
    //         TreeNode * pre = s.top();
    //         root->left = pre->right;
    //         root->right = pre;
    //     }
    //     return head;
    // }
    
    // *只有一侧的深度优先
    TreeNode * dfs(TreeNode * cur) {
        if (!cur->left)
        {
            return cur;
        }
        TreeNode * newNode = dfs(cur->left);
        cur->left->right = cur;
        cur->left->left = cur->right;
        cur->left = NULL;
        cur->right = NULL;
        return newNode;
    }
    
    TreeNode * upsideDownBinaryTree(TreeNode * root) {
        if (!root)
        {
            return NULL;
        }
        return dfs(root);
    }
};